﻿#ifdef _WIN32
#define _CRT_SECURE_NO_WARNINGS 1
#endif

// 长度最小的子数组
/*
class Solution
{
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int sum=0;
        int ans=INT_MAX;
        int n=static_cast<int>(nums.size());

        for(int left=0,right=0;right<n;++right)
        {
            // 进滑动窗口
            sum+=nums[right];
            // 判断
            while(sum>=target)
            {
                // 更新结果
                ans=std::min(ans,right-left+1);
                // 出窗口
                sum-=nums[left];
                ++left;
            }
        }

        return ans==INT_MAX?0:ans;
    }
};
*/

// 无重复字符的最长子串
// 同向双指针
/*
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        std::unordered_map<char,int> hash;
        int left=0;
        int right=0;
        int n=static_cast<int>(s.size());
        int ans=0;
        while(right<n)
        {
            // 入窗口
            hash[s[right]]++;
            // 判断
            while(hash[s[right]]>1)
            {
                // 出窗口
                hash[s[left]]--;
                ++left;
            }
            // 更新结果
            ans=std::max(ans,right-left+1);
            right++;
        }

        return ans;
    }
};
*/
// 暴力
/*
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {

        int n=static_cast<int>(s.size());
        unordered_set<char> hash;
        int ans=0;
        // 枚举所有子数组,每次枚举直到遇到重复才停止
        for(int i=0;i<n;++i)
        {
            hash.clear();
            for(int j=i;j<n;++j)
            {
                if(hash.find(s[j])==hash.end())
                {
                    hash.insert(s[j]);
                }
                else
                {
                    ans=std::max(ans,j-i);
                    break;
                }
            }
        }
        return ans;
    }
};
*/

// 最⼤连续 1 的个数 III 
/*
class Solution
{
public:
    // 暴力解法: 将该问题转换成子数组中零的个数不超过k个的长度
    int longestOnes(vector<int>& nums, int k)
    {
        int n=static_cast<int>(nums.size());
        int ans=0;

        for(int i=0;i<n;++i)
        {
            int j=i; // 枚举以i开头的子数组
            int zero=0; // 统计子数组出现的个数
            while(j<n)
            {
                if(0==nums[j]) // 遇到0则zero增加
                {
                    zero++;
                    if(zero>k) break; // 当zero大于k则无需继续统计
                }
                j++;
            }

            ans=std::max(ans,j-i); // 更新
        }

        return ans;
    }
};
*/
// 滑动窗口
/*
class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int ans=0;
        int zero=0;
        int left=0;
        int right=0;
        int n=static_cast<int>(nums.size());

        while(right<n)
        {
            if(0==nums[right]) zero++; // 入窗口统计0的个数

            while(zero>k) // 出窗口
            {
                if(0==nums[left]) zero--;
                left++;
            }

            ans=std::max(ans,right-left+1); // 更新

            right++;
        }

        return ans;
    }
};
*/
/*
class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int ret = 0;
        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
        {
            if (nums[right] == 0) zero++; // 进窗⼝
            while (zero > k) // 判断
                if (nums[left++] == 0) zero--; // 出窗⼝
            ret = max(ret, right - left + 1); // 更新结果
        }
        return ret;
    }
};
*/

// 将 x 减到 0 的最⼩操作数
/*
// 正难则反: 找出最长的子数组的长度,所有元素的和正好等于sum-x
int minOperations(vector<int>& nums, int x)
{   
    // 暴力
    if(nums.front() > x && nums.back() > x) return -1;
    int sum=accumulate(nums.begin(),nums.end(),0);

    int target=sum-x; // 确定目标值
    int ans=0;
    int n=static_cast<int>(nums.size());
    for(int i=0;i<n;++i) // 枚举所有子数组
    {
        int aim=0;
        for(int j=i;j<n;++j)
        {
            aim+=nums[j];
            // 更新策略
            if(aim==target) ans=std::max(ans,j-i+1);
            else if(aim>target) break;
        }
    }

    return n-ans;

     //int flag=false;
     //if(n==ans || ans==0) flag=true;
     //return flag?-1:n-ans;
}
*/
// 滑动窗口
/*
int minOperations(vector<int>& nums, int x)
{
    // 获取目标值
    int target=accumulate(nums.begin(),nums.end(),-x);

    if (target < 0) return -1;

    int ans=-1;
    int n=static_cast<int>(nums.size());

    for(int left=0,right=0,sum=0;right<n;++right)
    {
        sum+=nums[right]; // 入窗口

        while(sum>target) // 判断
        {
            sum-=nums[left++]; // 出窗口
        }

        if(sum==target) ans=std::max(ans,right-left+1); // 更新结果
    }

    if (ans == -1) return ans;
    else return n-ans;
}
*/
/*
class Solution
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int sum = 0;
        for (int a : nums) sum += a;
        int target = sum - x;
        // 细节问题
        if (target < 0) return -1;
        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            tmp += nums[right]; // 进窗⼝
            while (tmp > target) // 判断
                tmp -= nums[left++]; // 出窗⼝
            if (tmp == target) // 更新结果
                ret = max(ret, right - left + 1);
        }
        if (ret == -1) return ret;
        else return nums.size() - ret;
    }
};
*/

// 水果成篮
/*
 // 暴力: 求最大长度的子数组,该子数组中水果类型不超过2
    int totalFruit(vector<int>& fruits)
    {
        int ans=0;
        int n=static_cast<int>(fruits.size());
        for(int i=0;i<n;++i)
        {
            std::unordered_set<int> hash; // 记录子数组的类型个数
            int j=i; // 枚举所有子数组
            for(;j<n;++j)
            {
                hash.insert(fruits[j]); // 记录类型个数
                if(hash.size()>2) break; // 如果类型个数超过2则返回
            }
            ans=std::max(ans,j-i); // 更新结果
        }

        return ans;
    }
*/
// 滑动窗口
/*
class Solution
{
public:
    int totalFruit(vector<int>& fruits)
    {
        int n=static_cast<int>(fruits.size());
        int left=0;
        int right=0;
        int ans=0;
        std::unordered_map<int,int> hash;

        while(right<n)
        {
            hash[fruits[right]]++; // 入窗口
            while(hash.size() > 2) // 判断
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0)
                {
                    hash.erase(fruits[left]); // 出窗口
                }
                left++;
            }

            ans=std::max(ans,right-left+1);
            right++;
        }

        return ans;
    }
};
*/

// 字符串中的所有变位词
/*
class Solution
{
public:
    bool equal(std::unordered_map<char,int> &hash,std::unordered_map<char,int> &temp)
    {
        for(auto e:hash) if(e.second!=temp[e.first]) return false;
        return true;
    }
    // 暴力解法: 通过枚举所有长度为p.size()的字符串并通过hash计数来判断是否为p的变位词
    vector<int> findAnagrams(string s, string p)
    {
        if(s.size()<p.size()) return {};

        std::unordered_map<char,int> hash;
        for(auto ch : p) hash[ch]++; // 统计p的字符

        int n=static_cast<int>(s.size());
        std::vector<int> v;
        for(int i=0;i<n-p.size();++i)
        {
            std::unordered_map<char,int> temp;
            for(int j=i;j<i+p.size();++j)
            {
                temp[s[j]]++;
            }

            if(equal(hash,temp))
            {
                v.push_back(i);
            }
        }

        return v;
    }
};
*/
/*
class Solution
{
public:
    bool equal(std::unordered_map<char,int> &hash,std::unordered_map<char,int> &temp)
    {
        for(auto e:hash) if(e.second!=temp[e.first]) return false;
        return true;
    }
    // 滑动窗口
    vector<int> findAnagrams(string s, string p)
    {
        std::unordered_map<char,int> hash;
        for(auto ch : p) hash[ch]++; // 统计p的字符

        int left=0;
        int right=0;
        std::vector<int> v;
        std::unordered_map<char,int> temp;

        int n=static_cast<int>(s.size());
        while(right<n)
        {
            temp[s[right]]++; // 入窗口
            if(right-left+1>p.size()) // right>=left+p.size() // 如果窗口大小大于p.size()则出窗口
            {
            temp[s[left++]]--;
            }

            if (right - left + 1 == p.size()) // 只有窗口为p.size()才判断
                if (equal(hash, temp))
                    v.push_back(left);
            right++;
        }

        return v;
    }
};
*/
/*
class Solution
{
public:
    // 通过count记录有效字符个数来判断两个哈希表是否相等
    vector<int> findAnagrams(string s, string p)
    {
        int hp[26]={0};
        for(auto ch:p) hp[ch-'a']++; // 统计p中每一个字符的个数

        int hs[26]={0}; // 统计s区间中每一个字符的个数
        std::vector<int> v;
        for(int left=0,right=0,count=0;right<s.size();++right)
        {
            // 入窗口
            int in=s[right]-'a';
            hs[in]++;
            if(hs[in]<=hp[in]) count++; // 增加有效字符的个数

            // 判断
            if(right-left+1>p.size())
            {
                // 出窗口
                int out=s[left]-'a';
                if(hs[out]<=hp[out]) count--; // 减少有效字符的个数
                hs[out]--;
                left++;
            }

            // 更新结果
            if(count==p.size()) v.push_back(left); // 如果count等于p的长度则说明窗口的子串为变位词
        }

        return v;
    }
};
*/

// 串联所有单词的子串
/*
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        std::unordered_map<std::string,int> hashw;
        for(auto &str : words) hashw[str]++;

        int m=words.front().size(); // 一个单词的长度
        int word_size=words.size();
        std::vector<int> ans;

        for(int i=0;i<m;++i)
        {
            int left=i;
            int right=i;
            int count=0;
            int n=static_cast<int>(s.size()); // s的长度
            std::unordered_map<std::string,int> hashs;
            while(right<n-m+1)
            {
                // 入窗口
                std::string in_str=s.substr(right,m); // 获取进入窗口的字符串
                ++hashs[in_str];
                if( hashs[in_str]<=hashw[in_str] ) count++; // 更新hashs字符串的个数并判断count是否需要更新

                // 判断
                if( ((right-left)/m)+1 > word_size)
                {
                    // 出窗口
                    std::string out_str=s.substr(left,m); // 获取出窗口的字符串
                    if(hashs[out_str] <= hashw[out_str]) count--;
                    hashs[out_str]--;
                    left+=m;
                }

                // 更新结果
                if(count==word_size) ans.push_back(left);
                right+=m;
            }
        }

        return ans;
    }
};
*/

// 最小覆盖子串 
// 滑动窗口
/*
class Solution
{
public:
    string minWindow(string s, string t)
    {
        int hasht[128]={0}; int kinds=0; // kinds 字符种类
        for(auto ch : t) if(hasht[ch]++ == 0) kinds++;

        int hashs[128]={0};
        int begin=-1; int minlen=INT_MAX;

        for(int left=0,right=0,count=0;right<s.size();++right) // count表示有效字符的种类
        {
            // 入窗口
            char in=s[right];
            if(++hashs[in] == hasht[in]) count++;
            // 判断
            while(kinds==count)
            {
                // 更新结果
                if(right-left+1<minlen)
                {
                    begin=left;
                    minlen=right-left+1;
                }
                // 出窗口
                char out=s[left++];
                if(hashs[out]-- == hasht[out]) count--;
            }
        }
        if(begin==-1) return "";
        else return s.substr(begin,minlen);
    }
};
*/
/*
class Solution
{
public:
    string minWindow(string s, string t)
    {
        std::unordered_map<char,int> hasht;
        for(auto ch : t) hasht[ch]++;
        int kinds=hasht.size(); // 必须记录t字符的种类

        std::unordered_map<char,int> hashs;
        int begin=-1; int minlen=INT_MAX;

        for(int left=0,right=0,count=0;right<s.size();++right) // count表示有效字符的种类
        {
            // 入窗口
            char in=s[right];
            if(++hashs[in] == hasht[in]) count++; // 维护count
            // 判断
            while(kinds==count) // 不能hasht.size()==count,因为在hashs[in] == hasht[in]过程中size会增大
            {
                // 更新结果
                if(right-left+1<minlen)
                {
                    begin=left; // 更新起始下标
                    minlen=right-left+1; // 更新长度
                }
                // 出窗口
                char out=s[left++];
                if(hashs[out]-- == hasht[out]) count--;
            }
        }
        if(begin==-1) return "";
        else return s.substr(begin,minlen);
    }
};
*/

// 检查单词是否为句中其他单词的前缀
/*
// class Solution
// {
// public:
//     // 暴力解法:
//     int isPrefixOfWord(string sentence, string searchWord)
//     {
//         std::size_t pos=0;

//         while( (pos=sentence.find(searchWord,pos)) != std::string::npos )
//         {
//             if(pos == 0) return 1;
//             else if(sentence[pos-1] == ' ')
//             {
//                 int count=1;
//                 for(int i=0;i<static_cast<int>(pos);++i)
//                 {
//                     if(sentence[i]==' ') count++;
//                 }

//                 return count;
//             }
//         }

//         return -1;
//     }
// };
class Solution
{
public:
    // sentence中每一个单词与searchWord对比
    int isPrefixOfWord(std::string sentence, std::string searchWord)
    {
        // "i love eating burger", searchWord = "burg"
        int n=static_cast<int>(sentence.size());
        int right=0; int count=1;

        while(right<n)
        {
            int i=0;
            for(;i<searchWord.size();++i)
            {
                // sentence[index]是searchWord的前缀
                if(sentence[right]==' ') break;

                // 没有正确匹配,则比较下一个单词
                if(sentence[right]!=searchWord[i])
                {
                    while(sentence[right]!=' ')
                    {
                        right++;
                        if(right>=n) return -1; // 如果sentence遍历完成了则直接返回-1
                    }
                    break;
                }
                right++;
            }

            // searchWord是sentence[index]的前缀
            if(i>=searchWord.size()) return count;

            count++;
            right++;
        }

        return -1;
    }
};
*/
// 通过库函数stringstream+string.find解决:
/*
int isPrefixOfWord(string sentence, string searchWord)
    {
        std::stringstream ss(sentence);
        std::string word;
        int index=1;
        // 通过string流能够高效提取sentence中的每一个单词
        while(ss>>word)
        {
            // 如果searchWord是word的前缀则返回0
            if(0==word.find(searchWord)) return index;
            index++;
        }

        return -1;
    }
*/

// 定长子串中元音的最大数目
/*
class Solution
{
public:

    bool check(char ch)
    {
        return  ch=='a' ||
                ch=='i' ||
                ch=='e' ||
                ch=='o' ||
                ch=='u';
    }

    int maxVowels(string s, int k)
    {
        int ans=0;
        int n=static_cast<int>(s.size());
        for(int left=0,right=0,count=0;right<n;++right)
        {
            // 入窗口
            if(check(s[right])) count++;
            // 判断+出窗口
            if(right-left+1>k) if(check(s[left++])) count--;
            // 更新结果
            ans=std::max(ans,count);
        }
        return ans;
    }
};
*/